<TITLE>prob004: mystery shopper</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob004: mystery shopper</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.cuhk.hk/~jlee/">
          <B>Jim Ho Man Lee</B></A> 
          <ADDRESS><a href="mailto:jlee@cs.cuhk.hk">
          jlee@cs.cuhk.hk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Results </H3>

There are mutliple
solutions, one of which is found <a href="solution.data"> here </a>.

<P>
Jimmy Lee models each visit of a shopper by a unit square.  The square S_ij 
denotes the j-th visit of the i-th shopper.  We then need to
place 140 squares into a 35*4 table.
That square S_ij is placed at position (p,q) of the table means that
the saleslady p is visited in the q-th week by the i-th shopper as his/her
j-th visit.  A <TT> diffn </TT> constraint is used to enforce that the squares
do not overlap.  We also impose some other constraints, such as
<TT> element </TT> and <TT> alldifferent</TT>, to meet the rest of the requirements.

<P>
Using this modeling, the median execution time and the mean execution
time with the best and worst runs removed for E-GENET are 0.663
second and 0.725 second respectively while CHIP does not terminate within
10 hours.  H. Simonis later
developed a CHIP program for solving the problem using another
modeling with only the <TT> among</TT> constraint.  This program is also able to
solve the problem almost instantly.
The efficiency of Simonis's program is derived from
a domain specific value ordering heuristics tailor-made for
this problem.



</UL>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


